%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definición del tipo de documento.                                           %
% Posibles tipos de papel: a4paper, letterpaper, legalpapper                  %
% Posibles tamaños de letra: 10pt, 11pt, 12pt                                 %
% Posibles clases de documentos: article, report, book, slides                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt]{article}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Los paquetes permiten ampliar las capacidades de LaTeX.                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Paquete para inclusión de gráficos.
\usepackage{graphicx}

% Paquete para definir la codificación del conjunto de caracteres usado
% (latin1 es ISO 8859-1).
\usepackage[utf8]{inputenc}

% Paquete para definir el idioma usado.
%\usepackage[spanish]{babel}
\usepackage{float}

\usepackage{listings}
\usepackage[outdir=./]{epstopdf}

% Título principal del documento.
\title{		\textbf{Trabajo práctico 0: \\ Infraestructura básica \\[3ex]}}

% Información sobre los autores.
\author	{ 	Daddario Rubén, \textit{Padrón Nro. 83122}                      \\
            \texttt{ ruben.daddario@gmail.com }                             \\[3ex]            
            Amura Federico, \textit{Padrón Nro. 95202}							\\
			\texttt{federicoamura@gmail.com}           					    \\[3ex]
            \normalsize{Grupo Nro. X - 2do. Cuatrimestre de 2014}                       \\
            \normalsize{66.20 Organización de Computadoras}                           \\
            \normalsize{Facultad de Ingeniería, Universidad de Buenos Aires}          \\
       }

\date{Jueves 10 de septiembre de 2014}

\begin{document}

% Inserta el título.
\maketitle

% Quita el número en la primera página.
\thispagestyle{empty}

% Resumen
\begin{abstract}
El presente informe se corresponde al trabajo práctico número 0 de la asignatura 66.20 Organización de Computadoras. El trabajo consiste en desarrollar un programa portable con el objetivo de familiarizarse con el entorno de desarrollo a utilizar en la materia y las distintas herramientas disponibles.
\end{abstract}

\newpage

\tableofcontents

\newpage

\section{Introducción}

MIPS (Microprocessor without Interlocked Pipeline Stages) es un procesador con arquitectura RISC (reduced instruction set computer) desarrollado por MIPS Technologies. Este tipo de procesadores se encuentra en muchos sistemas embebidos y dispositivos de la actualidad como consolas de videojuegos, routers, etc. En particular, debido a que los diseñadores crearon un conjunto de instrucciones tan claro, los cursos sobre arquitectura de computadoras en unviersidades y escuelas técnicas a menudo se basan en la arquitectura MIPS.

Existen múltiples versiones de este procesador, siendo los más recientes MIPS32 y MIPS64, implementadas para 32 y 64 bits, respectivamente.

\section{Desarrollo}

El programa a elaborar es una implementación en ANSI C del comando nl de unix con un conjunto reducido de parámetros. Permite a grande rasgos enumerar las líneas de un documento a partir de un archivo de entrada.

\section{Diseño y detalles de implementación}

\subsection{Recursos utilizados}

Para resolver el problema planteado utilizamos la herramienta GXemul, para emular un entorno MIPS y el sistema operativo NetBSD. También utilizamos code::blocks para la codificación de la aplicación y un repositorio SVN para compartir el proyecto.  
\\[3ex]
Para implementar el programa utilizamos el lenguaje de programación C y para la realización del informe utilizamos \LaTeX{}.

\subsection{Diseño}

El programa se compone de múltiples archivos de cabecera .h con sus correspondientes archivos .c donde se realiza la implementación de los métodos utilizados.

\begin{center}
\texttt{tp0 [OPTION]...[FILE]...}
\end{center}

Las opciones pueden ser:
\begin{itemize}
\item -h, --help Print this message and quit
\item -s, --number-separator (mandatory argument)
\item -v, --starting-line-number (mandatory argument)
\item -i, --line-increment (mandatory argument)
\item -l, --join-blank-lines (mandatory argument)
\item -t, --non-blank
\end{itemize}


\subsection{Implementación}

\subsubsection{Portabilidad}

Para proveer portabilidad se implementaron las funciones en lenguaje C para dar soporte genérico a aquellos entornos que carezcan de una versión más específica. 

\begin{center}
comando utilizado: ./tp0 -s="-->" -v 1 --line-increment=1 prueba.txt
\end{center}

\begin{figure}[hbtp]
\caption{Salida de una ejecucion de prueba en NetBSD y MIPS}\label{fig001}
\includegraphics[width=1\textwidth]{ejecucionEnMIPS.eps}
\end{figure}

\begin{figure}[hbtp]
\caption{Salida de una ejecucion de prueba en Ubuntu y x86 64bits}\label{fig001}
\includegraphics[width=1\textwidth]{ejecucionEnUbuntu.eps}
\end{figure}

\subsubsection{Código y algoritmos}
El programa se compone de un archivo main con el punto de entrada al ejecutable y desde aquí se invócan al resto de los archivos que definen las estructuras de datos necesarias para la ejecución.



\newpage
\section{Mediciones. Corridas de prueba y resultados obtenidos }

La ejecución de los comandos time y gprof se efectuaron sobre un linux Ubuntu.
La primera prueba realizada se consistió en enviar por stdin al programa 462 archivos con un tamaño total aproximado de 6MB. A partir de aquí se midió el tiempo de ejecución con el comando time y el resultado obtenido es el que se muestra a continuación:

\begin{lstlisting}[language=bash]
 real   0m12.399s
 user   0m0.092s
 sys    0m0.100s
\end{lstlisting}
 
Mediante la opción -pg del compilador generamos información de profiling para ser analizada con gprof.
Una vez compilado el programa con este flag, volvemos a ejecutarlo con la misma carga de información.
Tras la ejecución se genera el archivo gmon.out que contendrá los datos de profiling.

\begin{lstlisting}[language=bash]
Flat profile:

Each sample counts as 0.01 seconds.
 no time accumulated

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  Ts/call  Ts/call  name    
  0.00      0.00     0.00   120353     0.00     0.00  applyLineHeader
  0.00      0.00     0.00   120353     0.00     0.00  isLineEmpty
  0.00      0.00     0.00   120353     0.00     0.00  shouldFormat
  0.00      0.00     0.00   114691     0.00     0.00  blankLinesToPrint
  0.00      0.00     0.00        1     0.00     0.00  freeOptions
  0.00      0.00     0.00        1     0.00     0.00  ignoreEquals
  0.00      0.00     0.00        1     0.00     0.00  parseOptions
  0.00      0.00     0.00        1     0.00     0.00  readFile
  0.00      0.00     0.00        1     0.00     0.00  readFiles
  0.00      0.00     0.00        1     0.00     0.00  startsWith
\end{lstlisting}

Si se analiza la salida, se puede observar que, aunque el profiler registra la cantidad de veces que una función es llamada, el tiempo registrado para estas funciones es 0.00. Esto puede deberse a que la cantidad total de tiempo en ejecución en el espacio de usuario es muy pequeña comparado con el tiempo utilizado en ejecución del kernel y por eso el tiempo se redondea a 0.00.  Esto se debe a que gprof toma medidas a intervalos fijos de tiempo durante la ejecución del programa, y estas mediciones se efectúan mientras se hace una llamada al kernel.

Con un archivo de 524.8MB donde se contabilizaron 8126959 líneas, los tiempos registrados son los siguientes:

TIME

\begin{lstlisting}[language=bash]
 real   17m10.302s
 user   0m5.460s
 sys	0m9.088s

\end{lstlisting}

GPROF 

\begin{lstlisting}[language=bash]
Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 50.00      0.08     0.08        1    80.00   160.00  readFile
 31.25      0.13     0.05  8126957     0.00     0.00  blankLinesToPrint
 12.50      0.15     0.02  8126960     0.00     0.00  applyLineHeader
  6.25      0.16     0.01  8126960     0.00     0.00  shouldFormat
  0.00      0.16     0.00  8126960     0.00     0.00  isLineEmpty
  0.00      0.16     0.00        1     0.00     0.00  freeOptions
  0.00      0.16     0.00        1     0.00     0.00  ignoreEquals
  0.00      0.16     0.00        1     0.00     0.00  parseOptions
  0.00      0.16     0.00        1     0.00   160.00  readFiles
  0.00      0.16     0.00        1     0.00     0.00  startsWith
\end{lstlisting}

En este caso tenemos información un poco mas significativa, sin embargo los tiempos siguen siendo muy bajos para obtener conclusiones.

Entendemos que la salida por pantalla es lo que consume la mayor cantidad de tiempo. Para verificar esto redirigimos la salida de la ejecución a un archivo y se genera un archivo de 605MB. Observamos ahora que los tiempos de time son los siguientes:

\begin{lstlisting}[language=bash]
 real   0m20.114s
 user   0m3.964s
 sys    0m1.792s
\end{lstlisting}

Es decir, tan solo 20 segundos.

\begin{figure}[hbtp]
\caption{Salida a archivo con input de 524.8MB}\label{fig001}
\includegraphics[width=1\textwidth]{time_long.eps}
\end{figure}

\newpage
\section{Mejoras}
Haremos una nueva ejecución para dos revisiones diferentes en nuestro repositorio de código. Calcularemos el speedup entre las revisiones 24 y la última, la 30. La mejora se introdujo en el método readFile que es el que consume la mitad
del tiempo de ejecución. Se reemplazó el uso de la función getline, que por otro lado no es ANSI C compatible, por el uso de la función fgets.

Ambas versiones deben ejecutarse con el mismo comando, en este caso sera enviando un archivo de 112,5MB llamado inputlong.txt unas 32 veces, de esta manera generamos una alta carga y tambien se evidencian de mejor manera los tiempos y cantidad de llamadas de cada metodo.
\begin{center}
time ./tp0 -s="-->" -v 1 --line-increment=1 inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt inputlong.txt > output.txt
\end{center}
La salida se va a enviar al archivo output.txt asi no interfiere en las mediciones la salida por pantalla que como vimos, genera unos aumentos en las mediciones de tiempo muy superiores a las del programa.
Con estas consideraciones, los tiempos medidos son:

Para la revision 24:
\begin{lstlisting}[language=bash]
 real	0m48.285s
 user	0m15.144s
 sys	0m8.793s
\end{lstlisting}

Para la revision 30:
\begin{lstlisting}[language=bash]
 real   0m43.132s
 user   0m12.267s
 sys    0m6.037s
\end{lstlisting}

Quedando:
\begin{displaymath}
   T_{24}=48.285s
 \end{displaymath}
 \begin{displaymath}
   T_{30}=43.132s
 \end{displaymath}

De esta manera, podemos calcular el SpeedUp que tuvimos con las mejoras aplicadas entre estas versiones.
\begin{displaymath}
   SU_{24,30}=\frac{T_{24}}{T_{30}}=\frac{48.285s}{43.132s}=1.12
 \end{displaymath}
 
 También podemos tener en cuenta la fracción de tiempo utilizada por la función mejorada calculando:

 \begin{displaymath}
 Speedup_{overall} = \frac{1}{(1-Fraccion_{mejorada}) + \frac{Fraccion_{mejorada}}{Speedup_{mejorado}}}
 \end{displaymath}

Aquí la fraccion de tiempo que se aplica la mejora es: 
 \begin{displaymath}
 Fraccion_{mejorada} = 50/100 = 0.5 
 \end{displaymath}
 
 Considerando que el metodo readFile se comporta aproximadamente 1.25 veces mas rapido, es decir, este metodo se mejoro con un SpeedUp de 1.25, calculamos el SpeedUp general considerando solo la mejora sobre la porcion de tiempo de ejecucion que corresponde a ese metodo.
 \begin{displaymath}
 Speedup_{mejorado} = 1.25
 \end{displaymath}
 
 Entonce tenemos:
 \begin{displaymath}
 Speedup_{overall} = \frac{1}{(1-0.5) + \frac{0.5}{1.25}} = 1.11
 \end{displaymath}

Lo cual nos da un SpeedUp total casi similar al anterior. La leve diferencia viene dada por los otros cambios que hubieron entre esas versiones, ademas de que la computadora cuenta con mas cargas al mismo tiempo que se realizan estas modificaciones, lo cual influye en las mediciones de tiempo finales.

\newpage
\section{Conclusiones}

A partir de este trabajo adquirimos experiencia en el uso de GXEmul para MIPS32, y el uso de \LaTeX{}.
También fue util el uso de herramientas como gprof y de otras herramientas de profiling que no incluimos en el presente informe, como por ejemplo kcachegrind.
Vimos que la salida por pantilla insume muchisimo tiempo en la ejecución del programa y que al enviar la salida a un achivo se disminuye considerablemente este lapso.

Vimos como establecer una conexión SSH entre dos hosts y transferir archivos a través de la conexión. Pudimos compilar mediante el uso de un makefile, generado a partir de la conversión de un archivo cpb de un proyecto de code::blocks.

Tuvimos ademas que lidiar con los warnings generados por el compilador y asegurarnos de utilizar funciones ANSI C estandar.

% Citas bibliográficas.
\begin{thebibliography}{99}

\bibitem{HEN00} J. L. Hennessy and D. A. Patterson, Computer Architecture. A Quantitative
Approach, 3ra Edicion, Morgan Kaufmann Publishers, 2000.
\bibitem{HEN01} Grupo de la materia http://groups.yahoo.com/group/orga6620/
\bibitem{HEN02} Wikipedia en.wikipedia.org
\bibitem{HEN03} http://www.ibm.com/developerworks/library/l-gnuprof.html

\end{thebibliography}

\end{document}